package com.zjsru.plan2024.oneday;

import java.util.ArrayList;
import java.util.List;

/**
 * 2961. 双模幂运算
 * @Author: cookLee
 * @Date: 2024-07-30
 */
public class GetGoodIndices {

    /**
     * 主
     * 0 <= i < variables.length
     * ((ai bi % 10)ci) % mi == target
     * \
     * 输入：variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
     * 输出：[0,2]
     * 解释：对于 variables 数组中的每个下标 i ：
     * 1) 对于下标 0 ，variables[0] = [2,3,3,10] ，(23 % 10)3 % 10 = 2 。
     * 2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(33 % 10)3 % 1 = 0 。
     * 3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(61 % 10)1 % 4 = 2 。
     * 因此，返回 [0,2] 作为答案。
     * \
     * 输入：variables = [[39,3,1000,1000]], target = 17
     * 输出：[]
     * 解释：对于 variables 数组中的每个下标 i ：
     * 1) 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(393 % 10)1000 % 1000 = 1 。
     * 因此，返回 [] 作为答案。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        GetGoodIndices getGoodIndices = new GetGoodIndices();
        int[][] variables = new int[][]{{2,3,3,10},{3,3,3,1},{6,1,1,4}};
        int target = 2;
        System.out.println(getGoodIndices.getGoodIndices(variables, target));
    }

    /**
     * 模拟
     *
     * @param variables 变量
     * @param target    目标
     * @return {@link List}<{@link Integer}>
     */
    public List<Integer> getGoodIndices(int[][] variables, int target) {
        int len = variables.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            int[] variable = variables[i];
            if (this.helper(this.helper(variable[0], variable[1], 10), variable[2], variable[3]) == target) {
                list.add(i);
            }
        }
        return list;
    }

    /**
     * 取模助手类
     *
     * @param i 我
     * @param j j
     * @param k k
     * @return int
     */
    private int helper(int i, int j, int k) {
        int ans = 1;
        while (j != 0) {
            if ((j & 1) != 0) {
                ans = ans * i % k;
            }
            i = i * i % k;
            j >>= 1;
        }
        return ans;
    }

}
